1. Technical Field
The present disclosure relates to the technical field of graphic rendering and, in particular, to a system and method for adaptive tessellation of a curve.
2. Description of the Related Art
In the context of the present disclosure, tessellating a curve involves approximating a curve (defined using some appropriate algebraic formula) as a series of simple straight line segments. It could be seen also as a process of sampling or quantization of a curve. From the continuous space of mathematical formula, tessellation involves the utilization of a certain amount of discrete straight line segments that approximate the curve itself. This is a typical problem when dealing with 2D graphics processing, and as such it is a crucial problem when dealing with the specific OpenVG standard promoted by the Khronos group because tessellation is a core feature of the standard itself. OpenVG is a standard API designed for hardware-accelerated 2D vector graphics. Vector graphics is the use of geometrical primitives such as lines, curves and shapes, which are all based on mathematical equations, to represent images in computer graphics.
Vector graphics formats are complementary to raster graphics, which is the representation of images as an array of pixels, as it is typically used for the representation of photographic images. It is aimed primarily at cell phones, media and gaming consoles such as the PlayStation 3, and other consumer electronic devices. It will help manufacturers create flashier user interfaces that are less dependent on energy-hungry CPUs. OpenVG is well suited to accelerating Flash or SVG sequences. The method disclosed herein is a novel proposal for solving a well-know problem that usually is addressed as the tessellation of a 2D Curve described in some algebraic form from a functional point of view as part of the path stage module of a compliant OpenVG 2D graphics pipeline.
In the field of 2D graphics, there are numerous algorithms to solve the problem of correctly tessellating a curve. What discriminates among different algorithms is the way the sampling is performed.
There are algorithms based on a fixed sampling. These methods are very simple to implement, but they are the ones that offer the worst results. A curve is always approximated in a fixed number of segments, for example 256 segments, no matter the particular curve formula and associated transformation. The main problem of these methods is the fact that a curve could be over-sampled or under-sampled depending on the curve type or transform applied to it. In the case of over-sampling, the curve is tessellated by higher numbers than is strictly required. Hence, many tessellated segments are not visible at all in the rendered scene, but the pipeline complexity is increased because it is indeed necessary to process them once they are generated. When an under-sampled curve is generated, it happens that the approximation done on the curve is poor; hence, it produces visible artifacts on the screen, i.e., the line segments become visible.
A completely different approach is to use an adaptive approach: The curve is in general approximated in a variable number of straight line segments according to a fixed threshold “f”, generally called the “flatness” of the curve. On these algorithms each produced line segment has always a deviation or distance from the real curve that is always no more than f.
Moreover, considering the position of the sampled points, there are algorithms in which the sampled points always lie on the exact curve and algorithms, such as the so-called “trapezoid tessellation”, in which the sampled points lie “near” the exact curve.